ট্রি (Tree)

ট্রি (Tree) একটি গুরুত্বপূর্ণ হায়ারার্কিক্যাল ডাটা স্ট্রাকচার যা ডাটা সংগঠিত করতে ব্যবহৃত হয়। এটি মূলত নোড (Node) দ্বারা গঠিত, যেখানে প্রতিটি নোডে ডাটা এবং একটি বা একাধিক চাইল্ড (child) নোডের রেফারেন্স থাকে। ট্রি ডাটা স্ট্রাকচার প্রাকৃতিকভাবে হায়ারার্কিক্যাল সম্পর্কের প্রতিনিধিত্ব করে, যেমন ফাইল সিস্টেম, পরিবার গাছ, অথবা ডেটাবেসের ইনডেক্সিং।

ট্রির মৌলিক ধারণা

• রুট (Root): ট্রির প্রথম নোড, যা পুরো ট্রির শীর্ষস্থান।
• নোড (Node): একটি একক উপাদান যা ডাটা ধারণ করে এবং অন্যান্য নোডের রেফারেন্স ধারণ করতে পারে।
• চাইল্ড (Child): একটি নোডের যে নোডগুলো তার সাথে সংযুক্ত থাকে, তাকে "চাইল্ড" নোড বলা হয়।
• প্যারেন্ট (Parent): একটি নোডের যে নোড তার সাথে সংযুক্ত, তাকে "প্যারেন্ট" নোড বলা হয়।
• লিফ নোড (Leaf Node): যেগুলি কোনো চাইল্ড নোড ধারণ করে না, তারা "লিফ" নোড হিসেবে পরিচিত।
• ডিপথ (Depth): একটি নোডের গভীরতা বা স্তর, যা তার প্যারেন্ট থেকে তার অবস্থান নির্দেশ করে।
• হাইট (Height): ট্রির সর্বোচ্চ স্তরের নোড পর্যন্ত গড় হিসেব।

ট্রি ইমপ্লিমেন্টেশন

এখন, আমরা একটি সাধারণ বাইনারি ট্রি (Binary Tree) ইমপ্লিমেন্ট করবো, যেখানে প্রতিটি নোড দুটি চাইল্ড নোড ধারণ করতে পারে (যেমন লেফট এবং রাইট চাইল্ড)। বাইনারি ট্রি একটি বিশেষ ধরনের ট্রি যেখানে প্রতিটি নোডের সর্বোচ্চ দুটি চাইল্ড নোড থাকে।

1. নোড ক্লাস (Node Class)

প্রথমে, ট্রির নোড ক্লাস তৈরি করতে হবে। এই ক্লাসে ডাটা, বাম (left) এবং ডান (right) চাইল্ড নোড থাকবে।

class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

2. বাইনারি ট্রি ক্লাস (Binary Tree Class)

এখন বাইনারি ট্রি ক্লাস তৈরি করতে হবে, যা বিভিন্ন অপারেশন যেমন ইনসার্ট (insert), ট্রাভার্স (traverse), ডিপথ (depth), হাইট (height) ইত্যাদি সম্পাদন করবে।

class BinaryTree {
    Node root;

    // Constructor to initialize an empty tree
    public BinaryTree() {
        root = null;
    }

    // Insert a new node into the binary tree
    public void insert(int data) {
        root = insertRec(root, data);
    }

    // Recursive function to insert a new node
    private Node insertRec(Node root, int data) {
        // If the tree is empty, return a new node
        if (root == null) {
            root = new Node(data);
            return root;
        }

        // Otherwise, recur down the tree
        if (data < root.data) {
            root.left = insertRec(root.left, data);  // Insert in left subtree
        } else if (data > root.data) {
            root.right = insertRec(root.right, data); // Insert in right subtree
        }

        // return the (unchanged) node pointer
        return root;
    }

    // Inorder traversal of the binary tree
    public void inorder() {
        inorderRec(root);
    }

    private void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);  // Traverse left subtree
            System.out.print(root.data + " ");  // Print the root data
            inorderRec(root.right); // Traverse right subtree
        }
    }

    // Preorder traversal of the binary tree
    public void preorder() {
        preorderRec(root);
    }

    private void preorderRec(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");  // Print the root data
            preorderRec(root.left);  // Traverse left subtree
            preorderRec(root.right); // Traverse right subtree
        }
    }

    // Postorder traversal of the binary tree
    public void postorder() {
        postorderRec(root);
    }

    private void postorderRec(Node root) {
        if (root != null) {
            postorderRec(root.left);  // Traverse left subtree
            postorderRec(root.right); // Traverse right subtree
            System.out.print(root.data + " ");  // Print the root data
        }
    }

    // Get the height of the binary tree
    public int height() {
        return heightRec(root);
    }

    private int heightRec(Node root) {
        if (root == null) {
            return 0;
        } else {
            // Recursively get the height of left and right subtrees and return the maximum
            int leftHeight = heightRec(root.left);
            int rightHeight = heightRec(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    // Get the depth of the tree (distance from root to any node)
    public int depth() {
        return depthRec(root);
    }

    private int depthRec(Node root) {
        if (root == null) {
            return 0;
        } else {
            int leftDepth = depthRec(root.left);
            int rightDepth = depthRec(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }
}

ক্লাসের ব্যাখ্যা:

1. insert(int data): নতুন একটি উপাদান বাইনারি ট্রিতে ইনসার্ট করার জন্য এই মেথডটি ব্যবহার করা হয়।
2. inorder(), preorder(), postorder(): ট্রির বিভিন্ন ট্রাভার্সাল মেথড (ইনঅর্ডার, প্রি-অর্ডার, পোস্ট-অর্ডার)।
3. height(): ট্রির সর্বোচ্চ উচ্চতা (height) নির্ধারণ করে।
4. depth(): ট্রির গভীরতা (depth) নির্ধারণ করে, তবে এই মেথডটি ট্রির গভীরতা বের করার সাধারণ একটি পদ্ধতি।

বাইনারি ট্রি ব্যবহার উদাহরণ

এখন আমরা বাইনারি ট্রির কিছু অপারেশন দেখব, যেমন ইনসার্ট, ট্রাভার্স, এবং হাইট নির্ধারণ।

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        // Insert elements into the binary tree
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        // Display the tree traversals
        System.out.println("Inorder traversal:");
        tree.inorder();  // Output: 20 30 40 50 60 70 80
        System.out.println();

        System.out.println("Preorder traversal:");
        tree.preorder(); // Output: 50 30 20 40 70 60 80
        System.out.println();

        System.out.println("Postorder traversal:");
        tree.postorder(); // Output: 20 40 30 60 80 70 50
        System.out.println();

        // Get the height of the tree
        System.out.println("Height of the tree: " + tree.height());  // Output: 3
    }
}

আউটপুট:

Inorder traversal:
20 30 40 50 60 70 80

Preorder traversal:
50 30 20 40 70 60 80

Postorder traversal:
20 40 30 60 80 70 50

Height of the tree: 3

সারাংশ

ট্রি (Tree) একটি শক্তিশালী ডাটা স্ট্রাকচার যা হায়ারার্কিক্যাল ডাটা সংরক্ষণের জন্য ব্যবহৃত হয়। বাইনারি ট্রি (Binary Tree) একটি বিশেষ ধরনের ট্রি যেখানে প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড থাকে। ট্রি ইমপ্লিমেন্ট করতে জাভাতে নোড এবং বাইনারি ট্রি ক্লাস তৈরি করা হয় এবং এর মাধ্যমে ট্রি অপারেশন যেমন ইনসার্ট, ট্রাভার্স, হাইট নির্ধারণ ইত্যাদি সম্পাদন করা যায়। বাইনারি ট্রি ট্রাভার্সাল অপারেশন যেমন ইনঅর্ডার, প্রি-অর্ডার এবং পোস্ট-অর্ডার সহজে সম্পাদিত হয় এবং এগুলি ট্রি সম্পর্কে মূল্যবান তথ্য প্রদান করে।

Tree হলো একটি অপ্রত্যক্ষ ডাটা স্ট্রাকচার যা গাণিতিকভাবে একটি connected acyclic graph হিসাবে সংজ্ঞায়িত করা যায়। একটি ট্রীতে এক বা একাধিক নোড থাকে, এবং প্রতিটি নোডের মধ্যে একটি প্যারেন্ট-চাইল্ড সম্পর্ক থাকে। এটি একটি hierarchical structure, যেখানে একক মূল (root) থেকে শুরু করে বিভিন্ন শাখার (branches) মাধ্যমে ডাটা সংগৃহীত হয়।

Tree এর মৌলিক ধারণা

• Root: একটি গাছের শীর্ষ বা মূল নোড (root node) থেকে অন্যান্য সমস্ত নোডে পৌঁছানো যায়।
• Parent-Child Relationship: প্রতিটি নোডের একটি প্যারেন্ট (parent) নোড থাকতে পারে, এবং সেই প্যারেন্ট নোডের এক বা একাধিক চাইল্ড (child) নোড থাকতে পারে।
• Leaf Node: একটি নোড যা কোন চাইল্ড নোড ধারণ করে না, সেটিকে leaf node বা পাতা নোড বলা হয়।
• Edge: দুইটি নোডের মধ্যে সংযোগ বা সম্পর্ককে edge বলা হয়।
• Subtree: একটি নোড এবং তার সমস্ত চাইল্ড নোডের সমষ্টি একটি subtree তৈরি করে।
• Depth: একটি নোডের depth হলো সেই নোডটি মূল (root) থেকে কতটা দূরে অবস্থিত।
• Height: গাছের উচ্চতা হলো সবচেয়ে গভীর পাতা নোড পর্যন্ত যাওয়ার পথের দৈর্ঘ্য।

Tree এর প্রকারভেদ

Tree বিভিন্ন ধরনের হতে পারে, প্রতিটি ধরনের গাছের নিজস্ব বৈশিষ্ট্য এবং ব্যবহার আছে। নীচে Tree এর কিছু প্রকারভেদ আলোচনা করা হলো:

1. Binary Tree (দ্বৈত গাছ)

একটি Binary Tree হল একটি গাছ যেখানে প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড নোড থাকতে পারে। এই গাছের মধ্যে একক প্যারেন্ট নোড থেকে দুটি চাইল্ড নোডে বিভক্ত করা হয়, এবং প্রতিটি চাইল্ড নোড আবার দুটি নোড ধারণ করতে পারে।

Binary Tree এর প্রকার:

• Full Binary Tree: একটি পূর্ণ দ্বৈত গাছ (Full Binary Tree) হলো এমন একটি গাছ, যেখানে প্রতিটি নোডের ঠিক দুইটি চাইল্ড নোড থাকে (অবশ্যই, leaf nodes এর জন্য দুইটি চাইল্ড থাকতে হবে না)।
• Complete Binary Tree: একটি পূর্ণাঙ্গ দ্বৈত গাছ (Complete Binary Tree) হলো এমন একটি গাছ যেখানে প্রতিটি স্তরের মধ্যে সমস্ত নোড পূর্ণ থাকে, এবং শেষ স্তরের নোডগুলি বাম থেকে ডানে পূর্ণ হয়।
• Perfect Binary Tree: একটি পারফেক্ট দ্বৈত গাছ (Perfect Binary Tree) হলো এমন একটি গাছ যেখানে সমস্ত নোডের মধ্যে সমান সংখ্যা চাইল্ড থাকে এবং সব পাতা একই স্তরে থাকে।

2. Binary Search Tree (BST)

Binary Search Tree (BST) হলো এমন একটি Binary Tree যেখানে প্রতিটি নোডের বাম চাইল্ডে ছোট মান এবং ডান চাইল্ডে বড় মান থাকে। এটি সোজা সোজা অনুসন্ধান এবং ডাটা ইনসার্ট করার জন্য একটি কার্যকরী গাছ।

BST এর বৈশিষ্ট্য:

• একটি BST এর বাম সাবট্রির সব নোডের মান প্যারেন্ট নোডের মান থেকে ছোট হবে।
• একটি BST এর ডান সাবট্রির সব নোডের মান প্যারেন্ট নোডের মান থেকে বড় হবে।
• এটি in-order traversal এ সাজানো ডাটা প্রদান করে।

3. AVL Tree (Adelson-Velsky and Landis Tree)

AVL Tree হলো একটি self-balancing binary search tree (BST), যেখানে গাছের প্রতিটি নোডের জন্য একটি balance factor থাকে। একটি নোডের balance factor হলো তার বাম এবং ডান সাবট্রির উচ্চতার পার্থক্য। যদি এটি 1, 0, বা -1 এর মধ্যে থাকে, তাহলে গাছটি ব্যালেন্সড থাকে। অন্যথায়, রোটেশন প্রয়োগ করে গাছটি ব্যালেন্স করা হয়।

AVL Tree এর বৈশিষ্ট্য:

• এটি সুনির্দিষ্ট সময়ের মধ্যে (O(log n)) সার্চ, ইনসার্ট এবং ডিলিট অপারেশন সম্পন্ন করতে সক্ষম।

4. Red-Black Tree

Red-Black Tree হলো একটি self-balancing binary search tree যা coloring rules ব্যবহার করে গাছের ব্যালেন্স বজায় রাখে। প্রতিটি নোডে একটি রঙ থাকে যা red বা black হতে পারে এবং কিছু নির্দিষ্ট নিয়ম অনুসরণ করা হয় যাতে গাছটি ব্যালেন্সড থাকে। এর মাধ্যমে গাছের অপারেশনগুলি দ্রুত এবং সুনির্দিষ্টভাবে সম্পন্ন করা যায়।

Red-Black Tree এর বৈশিষ্ট্য:

• প্রতিটি নোড red বা black হতে হবে।
• রুট নোডটি always black।
• কোনো red নোডের দুইটি red চাইল্ড থাকতে পারে না।
• প্রতিটি নোড থেকে তার ডাউনস্ট্রীম লিফ পর্যন্ত black height সমান হতে হবে।

5. B Tree

B Tree একটি self-balancing search tree যা sorted ডাটা ধারণ করে এবং balanced থাকে, তাই এটি দ্রুত অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশন সম্পন্ন করতে সক্ষম। এটি সাধারণত disk-based storage ব্যবহৃত ডাটাবেসে ব্যবহৃত হয়, যেখানে একটি গাছের উচ্চতা কম রাখতে হয়।

B Tree এর বৈশিষ্ট্য:

• এটি একটি multi-way tree যেখানে প্রতিটি নোডে একটি নির্দিষ্ট সংখ্যক চাইল্ড নোড থাকতে পারে।
• B Tree সাধারণত বৃহত্তর ডাটা স্টোরেজে ব্যবহৃত হয় যেখানে দ্রুত ডাটা ইনসার্ট ও ডিলিট করা প্রয়োজন।

6. Heap Tree

Heap Tree একটি সম্পূর্ণ বাইনারি গাছ (Complete Binary Tree), যেখানে প্রতিটি প্যারেন্ট নোডের মান তার সন্তানের চেয়ে বেশি (max-heap) বা কম (min-heap) থাকে।

Heap Tree এর প্রকার:

• Max Heap: প্রতিটি প্যারেন্ট নোডের মান তার সন্তানের মানের চেয়ে বড় বা সমান।
• Min Heap: প্রতিটি প্যারেন্ট নোডের মান তার সন্তানের মানের চেয়ে ছোট বা সমান।

Heap Tree সাধারণত priority queue এর জন্য ব্যবহৃত হয়, যেখানে সর্বোচ্চ বা সর্বনিম্ন মান বের করা হয় দ্রুত।

7. Trie (Prefix Tree)

Trie একটি বিশেষ ধরনের গাছ যা স্ট্রিং বা শব্দের মধ্যে অগ্রবর্তী অংশ (prefix) সংরক্ষণের জন্য ব্যবহৃত হয়। এটি সাধারণত dictionary বা autocomplete systems এ ব্যবহৃত হয়।

Trie এর বৈশিষ্ট্য:

• এটি একটি multi-way tree যেখানে প্রতিটি নোডে একটি চরিত্র থাকে।
• এটি স্ট্রিং সংরক্ষণ এবং অনুসন্ধানের জন্য কার্যকরী, যেখানে অনুসন্ধান সময় O(m), যেখানে m হল স্ট্রিং এর দৈর্ঘ্য।

সারাংশ

Tree হল একটি অপ্রত্যক্ষ ডাটা স্ট্রাকচার যা একটি হায়ারার্কিক্যাল কাঠামোতে ডাটা সংরক্ষণ করে। Binary Tree, Binary Search Tree (BST), AVL Tree, Red-Black Tree, B Tree, Heap Tree, এবং Trie হল Tree এর বিভিন্ন ধরনের যা বিভিন্ন সমস্যার সমাধান করার জন্য ব্যবহৃত হয়।

• Binary Trees ডাটা সন্নিবেশ এবং অনুসন্ধান দ্রুত করতে সহায়ক।
• AVL Tree এবং Red-Black Tree ব্যালেন্সড গাছ, যেখানে গাছের গঠন সঠিক রাখা হয়।
• Heap গাছগুলি প্রাধান্য বা সর্বাধিক বা সর্বনিম্ন উপাদান অনুসন্ধানের জন্য ব্যবহৃত হয়।
• Trie স্ট্রিং বা শব্দের সাথে সম্পর্কিত সমস্যাগুলির জন্য কার্যকরী।

এই গাছগুলি efficient searching, insertion, deletion এবং sorting অপারেশনগুলির জন্য গুরুত্বপূর্ণ।

1. Binary Tree

Binary Tree হল একটি বিশেষ ধরনের ডেটা স্ট্রাকচার যা প্রতি নোডে সর্বাধিক দুটি চাইল্ড (পুত্র) নোড ধারণ করতে পারে। এটি একটি হায়ারার্কিকাল ডেটা স্ট্রাকচার, যেখানে একটি রুট (root) নোড থাকে এবং প্রতিটি নোডের দুটি সাপোর্টিং নোড থাকতে পারে: লেফট চাইল্ড (left child) এবং রাইট চাইল্ড (right child)।

Binary Tree এর মূল উপাদান:

• Root: মূল নোড যেখানে থেকে বৃক্ষটি শুরু হয়।
• Parent Node: যে নোডের একটি বা দুটি চাইল্ড নোড থাকে।
• Child Node: একটি পিতার অধীনে থাকা নোড, যা লেফট বা রাইট চাইল্ড হতে পারে।
• Leaf Node: একটি নোড যার কোন চাইল্ড নেই।
• Subtree: একটি নোড এবং তার সমস্ত ডেসেনডেন্টরা মিলে একটি সাবট্রি তৈরি করে।

Binary Tree এর কাঠামো:

class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;

    public BinaryTree() {
        root = null;
    }

    // Inorder Traversal
    public void inorderTraversal(Node node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        System.out.print(node.data + " ");
        inorderTraversal(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("Inorder Traversal of Binary Tree:");
        tree.inorderTraversal(tree.root); // Output: 4 2 5 1 3
    }
}

ব্যাখ্যা:

• এখানে, একটি সাধারণ Binary Tree তৈরি করা হয়েছে যেখানে প্রতিটি নোডে একটি ডেটা এবং দুটি চাইল্ড (left এবং right) রয়েছে।
• inorderTraversal একটি জনপ্রিয় ট্রাভার্সাল মেথড যা বৃক্ষের নোডগুলো in-order সিকোয়েন্সে প্রদর্শন করে (লেফট, রুট, রাইট)।

2. Binary Search Tree (BST)

Binary Search Tree (BST) হল একটি বিশেষ ধরনের Binary Tree যেখানে প্রতিটি নোডের একটি নির্দিষ্ট সিকোয়েন্স থাকে:

• প্রতিটি নোডের বাম চাইল্ড এর মান ঐ নোডের মানের চেয়ে কম।
• প্রতিটি নোডের ডান চাইল্ড এর মান ঐ নোডের মানের চেয়ে বেশি।

BST একটি সার্চ অপটিমাইজড ট্রী যা ডেটা ইনসার্ট এবং সার্চ অপারেশনকে দ্রুত করতে সাহায্য করে, কারণ প্রতিটি নোডে একটি নির্দিষ্ট সিকোয়েন্স থাকে।

BST এর প্রধান অপারেশন:

• Insertion: নতুন মান যোগ করা।
• Deletion: একটি নোড মুছে ফেলা।
• Search: একটি নির্দিষ্ট মান খোঁজা।
• Traversal: বৃক্ষের নোডগুলো ভিজিট করা (ইন-অর্ডার, প্রি-অর্ডার, পোস্ট-অর্ডার)।

BST এর কাঠামো:

class BSTNode {
    int data;
    BSTNode left, right;

    public BSTNode(int data) {
        this.data = data;
        left = right = null;
    }
}

public class BinarySearchTree {
    BSTNode root;

    public BinarySearchTree() {
        root = null;
    }

    // Insert a node in BST
    public void insert(int data) {
        root = insertRec(root, data);
    }

    private BSTNode insertRec(BSTNode root, int data) {
        if (root == null) {
            root = new BSTNode(data);
            return root;
        }

        if (data < root.data) {
            root.left = insertRec(root.left, data);
        } else if (data > root.data) {
            root.right = insertRec(root.right, data);
        }

        return root;
    }

    // Inorder Traversal
    public void inorderTraversal(BSTNode node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        System.out.print(node.data + " ");
        inorderTraversal(node.right);
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println("Inorder Traversal of Binary Search Tree:");
        tree.inorderTraversal(tree.root);  // Output: 20 30 40 50 60 70 80
    }
}

ব্যাখ্যা:

• insert: একটি নতুন মান BST-তে যোগ করার জন্য এই মেথডটি ব্যবহৃত হয়। প্রতিটি নতুন নোড সংযোজনের সময়, BST নিয়ম অনুসরণ করে সঠিক স্থানে যোগ করা হয়।
• inorderTraversal: inorder ট্রাভার্সাল মেথডটি BST-তে গঠিত নোডগুলো ইন-অর্ডারে প্রদর্শন করে, যা BST এ সজ্জিত ডেটাকে সঠিকভাবে ক্রমানুসারে প্রদর্শন করে।

3. Binary Tree এবং Binary Search Tree এর পার্থক্য

4. Binary Tree এবং BST এর ব্যবহারিক প্রয়োগ

• Binary Tree:
  • হিয়ারার্কিক্যাল ডেটা: ফাইল সিস্টেমের গঠন বা বিভাগীয় কাঠামো।
  • অ্যালগরিদমে ব্যবহার: হাফ (heap) বা প্রিভিউ কাঠামো (priority queue) গঠন করতে।
• Binary Search Tree (BST):
  • ডেটা অনুসন্ধান: দ্রুত ডেটা অনুসন্ধান এবং সন্নিবেশ জন্য।
  • ডেটা অর্গানাইজেশন: মেমরি ব্যবস্থাপনা এবং ডেটা ফিল্টারিংয়ের জন্য।
  • পরিসংখ্যান বিশ্লেষণ: ডেটা সেটের ট্রেন্ড, পরিসংখ্যান বা সঠিক মান খোঁজা।

সারাংশ

Binary Tree এবং Binary Search Tree (BST) হল গাছের (tree) দুই ধরনের জনপ্রিয় ডেটা স্ট্রাকচার। Binary Tree একটি সাধারণ গঠন যেখানে প্রতিটি নোডের দুটি চাইল্ড থাকে এবং এটি সাধারণত ট্রাভার্সাল অপারেশনগুলিতে ব্যবহৃত হয়। অন্যদিকে, Binary Search Tree (BST) একটি বিশেষ ধরনের বাইনারি ট্রি যা ডেটাকে সঠিকভাবে সাজিয়ে রাখে, যা সার্চ এবং সন্নিবেশ অপারেশনগুলিকে কার্যকরী এবং দ্রুত করে তোলে। DBMS, গেম ডেভেলপমেন্ট, ইন্টারনেট সার্চ ইঞ্জিন এবং বিভিন্ন অ্যালগরিদমে এই ডেটা স্ট্রাকচার দুটি গুরুত্বপূর্ণ ভূমিকা পালন করে।

Tree Traversal হল একটি গাছের (tree) সমস্ত নোডে পৌঁছানোর এবং তাদের পরিদর্শন করার প্রক্রিয়া। গাছের নোডগুলোতে ট্রাভার্স করার তিনটি প্রধান পদ্ধতি হল In-order, Pre-order, এবং Post-order traversal। প্রতিটি পদ্ধতির মধ্যে একেকটি নোডের পরিদর্শন করার সিকোয়েন্স আলাদা।

এখানে, আমরা এই তিনটি ট্রাভার্সাল পদ্ধতি এবং তাদের Java তে কিভাবে প্রয়োগ করা যায়, তা আলোচনা করব।

1. Tree Traversal Overview

Tree Traversal হল সেই প্রক্রিয়া যার মাধ্যমে আমরা গাছের প্রতিটি নোডে একবার পৌঁছানোর চেষ্টা করি। গাছের প্রতিটি নোডে পরিদর্শন করার জন্য তিনটি সাধারণ কৌশল হলো:

• Pre-order Traversal: প্রথমে রুট (root), তারপর বাম সাবট্রি (left subtree), এবং পরে ডান সাবট্রি (right subtree)।
• In-order Traversal: প্রথমে বাম সাবট্রি (left subtree), তারপর রুট (root), এবং পরে ডান সাবট্রি (right subtree)।
• Post-order Traversal: প্রথমে বাম সাবট্রি (left subtree), তারপর ডান সাবট্রি (right subtree), এবং পরে রুট (root)।

প্রতিটি পদ্ধতিতে রুট নোডের অবস্থান এবং তার চারপাশের নোডগুলোর পরিদর্শন সিকোয়েন্সের মধ্যে পার্থক্য রয়েছে।

2. Pre-order Traversal

Pre-order Traversal এ প্রথমে রুট নোড পরিদর্শন করা হয়, তারপর বাম সাবট্রি এবং শেষে ডান সাবট্রি।

2.1. Pre-order Traversal Example

class TreeNode {
    int data;
    TreeNode left, right;

    // Constructor to create a new node
    public TreeNode(int data) {
        this.data = data;
        left = right = null;
    }
}

public class PreOrderTraversal {
    TreeNode root;

    // Pre-order Traversal: root, left, right
    public void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        
        // Visit root
        System.out.print(node.data + " ");
        
        // Visit left subtree
        preOrder(node.left);
        
        // Visit right subtree
        preOrder(node.right);
    }

    public static void main(String[] args) {
        PreOrderTraversal tree = new PreOrderTraversal();
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        
        System.out.println("Pre-order Traversal:");
        tree.preOrder(tree.root);
    }
}

ব্যাখ্যা:

• Pre-order Traversal এর মধ্যে প্রথমে রুট নোডে চলে যাওয়া হয়, তারপর বাম সাবট্রি এবং পরিশেষে ডান সাবট্রি পরিদর্শন করা হয়।
• preOrder(node) মেথডটি গাছের প্রতিটি নোডে পৌঁছানোর জন্য রিকার্শন ব্যবহার করছে।

আউটপুট:

Pre-order Traversal:
1 2 4 5 3

3. In-order Traversal

In-order Traversal এ প্রথমে বাম সাবট্রি পরিদর্শন করা হয়, তারপর রুট নোডে পৌঁছানো হয় এবং শেষে ডান সাবট্রি পরিদর্শন করা হয়।

3.1. In-order Traversal Example

public class InOrderTraversal {
    TreeNode root;

    // In-order Traversal: left, root, right
    public void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        
        // Visit left subtree
        inOrder(node.left);
        
        // Visit root
        System.out.print(node.data + " ");
        
        // Visit right subtree
        inOrder(node.right);
    }

    public static void main(String[] args) {
        InOrderTraversal tree = new InOrderTraversal();
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        
        System.out.println("In-order Traversal:");
        tree.inOrder(tree.root);
    }
}

ব্যাখ্যা:

• In-order Traversal এ প্রথমে বাম সাবট্রি পরিদর্শন করা হয়, তারপর রুট নোডে চলে আসা হয়, এবং শেষে ডান সাবট্রি পরিদর্শন করা হয়।
• inOrder(node) মেথডটি গাছের প্রতিটি নোডে পৌঁছানোর জন্য রিকার্শন ব্যবহার করছে।

আউটপুট:

In-order Traversal:
4 2 5 1 3

4. Post-order Traversal

Post-order Traversal এ প্রথমে বাম সাবট্রি পরিদর্শন করা হয়, তারপর ডান সাবট্রি পরিদর্শন করা হয় এবং শেষে রুট নোড পরিদর্শন করা হয়।

4.1. Post-order Traversal Example

public class PostOrderTraversal {
    TreeNode root;

    // Post-order Traversal: left, right, root
    public void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        
        // Visit left subtree
        postOrder(node.left);
        
        // Visit right subtree
        postOrder(node.right);
        
        // Visit root
        System.out.print(node.data + " ");
    }

    public static void main(String[] args) {
        PostOrderTraversal tree = new PostOrderTraversal();
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        
        System.out.println("Post-order Traversal:");
        tree.postOrder(tree.root);
    }
}

ব্যাখ্যা:

• Post-order Traversal এ প্রথমে বাম সাবট্রি পরিদর্শন করা হয়, তারপর ডান সাবট্রি পরিদর্শন করা হয়, এবং শেষে রুট নোড পরিদর্শন করা হয়।
• postOrder(node) মেথডটি গাছের প্রতিটি নোডে পৌঁছানোর জন্য রিকার্শন ব্যবহার করছে।

আউটপুট:

Post-order Traversal:
4 5 2 3 1

5. Comparison of Tree Traversal Techniques

সারাংশ

Tree Traversal হল গাছের সমস্ত নোড পরিদর্শন করার প্রক্রিয়া। In-order, Pre-order, এবং Post-order হল এর তিনটি প্রধান পদ্ধতি, এবং এগুলির মধ্যে প্রতিটি পদ্ধতি গাছের নোডগুলো পরিদর্শন করার আলাদা সিকোয়েন্স প্রদান করে:

• Pre-order Traversal: Root -> Left -> Right
• In-order Traversal: Left -> Root -> Right
• Post-order Traversal: Left -> Right -> Root

এই তিনটি পদ্ধতির মধ্যে In-order সাধারণত binary search trees (BST) এ ব্যবহার করা হয়, Pre-order গাছের কপি বা এক্সপ্রেশন ট্রি ইভালুয়েশনে ব্যবহৃত হয়, এবং Post-order গাছ মুছে ফেলা বা পোস্টফিক্স এক্সপ্রেশন ইভালুয়েশনে ব্যবহৃত হয়।

এই ট্রাভার্সাল পদ্ধতিগুলি Java তে খুব সহজে বাস্তবায়িত করা যায় এবং গাছের অপারেশনগুলোকে আরও কার্যকরী করে তোলে।

AVL Tree এবং অন্যান্য Balanced Trees হল Binary Search Tree (BST) এর একটি বিশেষ ধরনের ডাটা স্ট্রাকচার যা self-balancing হয়। এতে প্রতিটি নোডের জন্য একটি নির্দিষ্ট balance factor থাকে যা নিশ্চিত করে যে গাছের উচ্চতা কখনোই খুব বেশি বৃদ্ধি পায় না। এর ফলে, গাছের অপারেশনগুলো (যেমন insertion, deletion, এবং searching) সবসময় O(log n) টাইম কমপ্লেক্সিটি সহ সম্পাদিত হয়।

এই গাইডে আমরা AVL Tree এবং Balanced Trees এর কার্যকারিতা, কাঠামো, এবং জাভাতে এর বাস্তবায়ন নিয়ে আলোচনা করব।

1. Balanced Tree এর ধারণা

Balanced Trees হল এমন একটি ডাটা স্ট্রাকচার যেখানে গাছের প্রতিটি নোডের বাম এবং ডান সাবট্রি এর উচ্চতার মধ্যে একটি নির্দিষ্ট সীমার মধ্যে পার্থক্য থাকে। এর ফলে গাছের গঠন কেবল একে অপরের থেকে সমানভাবে সোজা হয়ে থাকে, যা গাছের অপারেশনগুলোকে অপটিমাইজ করে।

AVL Tree এর মধ্যে এমন একটি বিশেষ ধরনের ব্যালেন্সিং অ্যালগরিদম রয়েছে যা গাছের উচ্চতা নিশ্চিতভাবে নিয়ন্ত্রণ করে রাখে।

2. AVL Tree (Adelson-Velsky and Landis Tree)

AVL Tree হল একটি self-balancing binary search tree যেখানে প্রতিটি নোডের জন্য balance factor থাকে। একটি নোডের balance factor হল তার বাম সাবট্রি এবং ডান সাবট্রি এর উচ্চতার পার্থক্য। যদি এটি 1, 0, বা -1 থাকে, তবে গাছটি ব্যালেন্সড থাকে; অন্যথায়, গাছটিকে পুনরায় ব্যালেন্স করতে হবে।

• Balance Factor: BF = Height(Left Subtree) - Height(Right Subtree)
• AVL Tree Rules:
  • এক নোডের বাম এবং ডান সাবট্রির উচ্চতার পার্থক্য সর্বাধিক 1 হতে পারে।

2.1. Rotation Operations in AVL Tree

এখানে চারটি rotation অপারেশন আছে যা AVL গাছের ব্যালেন্স ঠিক রাখতে সাহায্য করে:

1. Left Rotation (Single Rotation)
2. Right Rotation (Single Rotation)
3. Left-Right Rotation (Double Rotation)
4. Right-Left Rotation (Double Rotation)

2.2. AVL Tree Implementation in Java

class AVLTree {
    class Node {
        int data;
        Node left, right;
        int height;

        public Node(int data) {
            this.data = data;
            this.height = 1; // Initial height is 1 (for new nodes)
        }
    }

    private Node root;

    // Utility method to get height of a node
    private int height(Node node) {
        return (node == null) ? 0 : node.height;
    }

    // Utility method to get balance factor of a node
    private int getBalanceFactor(Node node) {
        return (node == null) ? 0 : height(node.left) - height(node.right);
    }

    // Right rotation
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // Perform rotation
        x.right = y;
        y.left = T2;

        // Update heights
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x; // New root
    }

    // Left rotation
    private Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // Perform rotation
        y.left = x;
        x.right = T2;

        // Update heights
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y; // New root
    }

    // Insert a node
    public void insert(int data) {
        root = insert(root, data);
    }

    private Node insert(Node node, int data) {
        if (node == null) {
            return new Node(data);
        }

        // Perform the normal BST insertion
        if (data < node.data) {
            node.left = insert(node.left, data);
        } else if (data > node.data) {
            node.right = insert(node.right, data);
        } else {
            return node; // Duplicates are not allowed
        }

        // Update the height of this ancestor node
        node.height = 1 + Math.max(height(node.left), height(node.right));

        // Get the balance factor of this ancestor node to check whether it became unbalanced
        int balance = getBalanceFactor(node);

        // If the node becomes unbalanced, then there are 4 cases

        // Left Left Case
        if (balance > 1 && data < node.left.data) {
            return rightRotate(node);
        }

        // Right Right Case
        if (balance < -1 && data > node.right.data) {
            return leftRotate(node);
        }

        // Left Right Case
        if (balance > 1 && data > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Left Case
        if (balance < -1 && data < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node; // Return the (unchanged) node pointer
    }

    // Preorder traversal of the tree
    public void preorder() {
        preorder(root);
    }

    private void preorder(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preorder(node.left);
            preorder(node.right);
        }
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(15);
        tree.insert(25);

        System.out.print("Preorder traversal: ");
        tree.preorder(); // Output: 20 10 15 30 25
    }
}

2.3. Explanation:

• Insert Operation: ইনসার্ট করার সময়, গাছটি self-balancing হয় এবং যথাযথ রোটেশন অপারেশনগুলি প্রয়োগ হয়।
• Balancing the Tree: গাছের যেকোনো নোডের balance factor যদি 1 বা -1 এর বাইরে চলে যায়, তখন রোটেশন প্রয়োগ করা হয়।
• Traversal: preorder() মেথডের মাধ্যমে গাছের সমস্ত উপাদান preorder traversal অনুসারে প্রদর্শন করা হয়।

3. Balanced Trees - Other Types

Balanced Trees এর মধ্যে বিভিন্ন ধরনের গাছ রয়েছে, যেমন Red-Black Tree, AVL Tree, এবং Splay Tree। তবে, AVL Tree হল একটি সবচেয়ে জনপ্রিয় এবং কার্যকরী self-balancing tree। এটি গাছের গঠনকে সব সময় ব্যালেন্সড রাখতে সাহায্য করে।

3.1. Red-Black Tree

• এটি একটি বিশেষ ধরনের ব্যালেন্সড বাইনারি সার্চ ট্রি যেখানে প্রতিটি নোডের একটি রঙ (লাল বা কালো) থাকে এবং নির্দিষ্ট নিয়ম অনুসরণ করে গাছটি ব্যালেন্স করা হয়। Red-Black Tree খুব দ্রুত অ্যাড/ডিলিট অপারেশন পরিচালনা করে।

3.2. Splay Tree

• এটি একটি অটো-ব্যালেন্সিং বাইনারি সার্চ ট্রি যেখানে নোডগুলিকে স্লাইড করা হয়, তবে এর পারফরম্যান্স সবসময় সেরা নয়।

সারাংশ

AVL Tree হল একটি self-balancing binary search tree, যেখানে প্রতিটি নোডের balance factor চেক করা হয় এবং সেই অনুযায়ী রোটেশন প্রয়োগ করা হয়। এর সাহায্যে আপনি বাইনারি সার্চ ট্রির অপারেশনগুলোকে O(log n) টাইমে সম্পাদন করতে পারেন। অন্যান্য Balanced Trees এর মধ্যে Red-Black Tree এবং Splay Tree রয়েছে যা ব্যালেন্সড গাছের ক্ষেত্রে বিভিন্ন ধরনের সমাধান প্রদান করে।

AVL Tree একটি খুবই কার্যকরী ডাটা স্ট্রাকচার যখন আপনাকে ডাটা সার্চ, ইনসার্ট এবং ডিলিট করার অপারেশন দ্রুত এবং সুনির্দিষ্টভাবে সম্পাদন করতে হয়।